import os
import sys


# 请在此输入您的代码

def dfs(depth, last_value, tot, mul):
    if depth == n:
        if tot > 2 * path[-1]:
            ans[mul] += 1
        return

    for i in range(last_value + 1, 100001):
        if mul * (i ** (n - depth)) <= 100000:
            path.append(i)
            dfs(depth + 1, i, tot + i, mul * i)

            path.pop()
        else:
            break


ans = [0] * 100001
t, n = map(int, input().split())
path = []
dfs(0, 0, 0, 1)

for i in range(100001):
    ans[i] += ans[i - 1]

for _ in range(t):
    l, r = map(int, input().split())
    print(ans[r] - ans[l - 1])
